/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package alternate;

import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 * The Class ID3 Algorithm runs the ID3 Algorithm on a given Table.
 * @author Galina Bulgakova
 * @author Peter Weirich
 */
public class ID3Algorithm 
{
    private Map<String,ArrayList> table;
    private int numberOfAttributes;
    private int numberOfRows;
    private String targetAttribute;
    private String targetAttributeValue;
    private double targetInformation;
    private String logFileName = "log.txt";
    
    /**
     * 
     * @param table The Table the ID3 Algorithm should use.
     */
    public ID3Algorithm(Map<String,ArrayList> tempTable, String tempTargetAttribute, String tempTargetAttributeValue) throws IOException
    {
        this.table = tempTable;
        this.targetAttribute = tempTargetAttribute;
        this.targetAttributeValue = tempTargetAttributeValue;
        this.numberOfAttributes = this.countTableAttributes();
        this.numberOfRows = this.countTableRows();
        this.targetInformation = calculateTargetInformation();
    }
    
    // Getter and Setter
    public int getNumberOfAttributes()
    {
        return this.numberOfAttributes;
    }
    
    public int getNumberOfRows()
    {
        return this.numberOfRows;
    }
    
    public String getTargetAttribute()
    {
        return this.targetAttribute;
    }
    
    public String getTargetAttributeValue()
    {
        return this.targetAttributeValue;
    }
    
    /**
     * Get the Table
     * @return <Map,ArrayList>
     */
    public Map<String,ArrayList> getTable()
    {
        return this.table;
    }
    
    public void setNumberOfAttributes(int value)
    {
        this.numberOfAttributes = value;
    }
    
    public void setNumberOfRows(int value)
    {
        this.numberOfRows = value;
    }
    
    public void setTargetAttribute(String value)
    {
        this.targetAttribute = value;
    }
    
    /**
     * Set the Target Value
     * @param value 
     */
    public void setTargetAttributeValue(String value)
    {
        this.targetAttributeValue = value;
    }
    
    public void setLogFileName(String value)
    {
        this.logFileName = value;
    }
        
    /**
     * Rekursive method to calculate the ID3 tree
     * 
     */
    public void buildTree(Map<String, ArrayList> tempMap, int depth) throws IOException
    {
        ID3Algorithm id3 = new ID3Algorithm(tempMap, this.targetAttribute, this.targetAttributeValue);
        Map<String,Double> infoGain = id3.calculateHighestInformationGain();
        
        if(infoGain != null)
        {
            for(String elem : infoGain.keySet())
            {
                System.out.println(elem);
                Map<String, Map<String, ArrayList>> split = id3.splitTable(elem);
                for(String rekName : split.keySet())
                {         
                    log("Zweig für " + elem + " mit Wert " + rekName + "---------------------------" +"\n");
                    for(int i = 0; i < depth; i++)
                    {
                        System.out.print("\t");
                    }
                    if(depth == 0)
                    {
                        System.out.print("   |-");
                    }
                    else
                    {
                        System.out.print("  |-");
                    }
                    System.out.print(rekName + " -> ");
                    this.buildTree(split.get(rekName), depth + 1);
                }
            }
        }
        else
        {
            System.out.println(tempMap.get(this.targetAttribute).get(0));
        }
    }

    /**
     * Calculates the entropy of every double value in array.
     * @param tempProbabilities All double values the entropy should be computed for.
     * @return Entropy of all elements as double value.
     */
    public double calculateEntropy(double[] tempProbabilities) throws IOException
    {
        double totalEntropy = 0;
        for(int i = 0; i < tempProbabilities.length;i++)
        {
            if(tempProbabilities[i] != 0)
            {
                totalEntropy += (double)tempProbabilities[i] * (Math.log((double)tempProbabilities[i])/Math.log(2));
            }
            else
            {
                log("0\n");
                return 0;
            }
        }
        try
        {
            log(totalEntropy * (-1) +"\n");
        }
        catch(Exception ex)
        {
            System.out.println("Problems logging the Entropy " + ex);
        }
        return totalEntropy * (-1);
    }
    
    /**
     * Calculates the weighted Information for an attribute
     * @return 
     */
    public Map<String,Double> calculateAttributesWeightedInformation() throws IOException
    {
        Map<String,Double> attributesWeightedInformation = new HashMap<String, Double>();
        Set<String> attributes = this.table.keySet();
        
        for(String elem : attributes) // Iterate through all attributes in the table
        {
            if(!elem.equals(this.targetAttribute))    // leave out the target attribute
            {
                // Count the different Attribute values
                Map<String,Integer> countedDifferentAttributeValues = this.countAttributeValues(elem);
                // Determine the "hit" and "miss" rate
                Map<String,int[]> comparedToTarget = this.compareAttributeAndTarget(elem);
                
                double tempAttributeValueWeightedEntropy = 0;
                
                log("Entropieberechnung für " + elem + "\n");
                for(String attributeValue : countedDifferentAttributeValues.keySet())
                {
                    log(attributeValue+ " ");
//                    System.out.println("Attribute: " + elem + "  |  Attribut Name: " + attributeValue + "  |  Anzahl: " + countedDifferentAttributeValues.get(attributeValue));
//                    System.out.println("Hits: " + comparedToTarget.get(attributeValue)[0] + "  |  Misses: " + comparedToTarget.get(attributeValue)[1]);
                    
                    double weight = (double)countedDifferentAttributeValues.get(attributeValue) / (double)this.numberOfRows;
//                    System.out.println("Weight: " + weight);
                    double hit = (double)(comparedToTarget.get(attributeValue)[0] / (double)countedDifferentAttributeValues.get(attributeValue));
                    double miss = (double)(comparedToTarget.get(attributeValue)[1]/ (double)countedDifferentAttributeValues.get(attributeValue));
 
                    tempAttributeValueWeightedEntropy += (double)(weight * this.calculateEntropy(new double[]{hit,miss}));
                }
                attributesWeightedInformation.put(elem, tempAttributeValueWeightedEntropy);
                log("Gewichtete Information für " + elem + " beträgt " + tempAttributeValueWeightedEntropy + "\n");
            }
        }
            
        return attributesWeightedInformation;
    }
    
    /**
     * Calculates the Information of the target attribute
     * @return Info(T) as double
     */
    public double calculateTargetInformation() throws IOException
    {        
        Map<String,Integer> attributeFrequency = this.countAttributeValues(this.targetAttribute);
        
        int targetValueCount = 0;
        int noTargetValueCount = 0;
        
        for(String attributeValue : attributeFrequency.keySet())
        {
            if(attributeValue.equals(this.targetAttributeValue))
            {
                targetValueCount += attributeFrequency.get(attributeValue);
            }
            else
            {
                noTargetValueCount += attributeFrequency.get(attributeValue);
            }
        }
        log("Entropie des Zielattributs:");
        double returnValue = (double)this.calculateEntropy(new double[]{(double)targetValueCount/this.numberOfRows, (double)noTargetValueCount/this.numberOfRows});
        return returnValue;
    }
    
    /**
     * Calculates the information gain
     * @return Information gain.
     */
    public Map<String,Double> calculateHighestInformationGain() throws IOException
    {
        Map<String,Double> weightedInformation = this.calculateAttributesWeightedInformation();
        
        double highestInformationGain = 0;
        String highestInformationAttributeName = "";
        
        for(String attributeName : weightedInformation.keySet())
        {
            if((this.targetInformation - weightedInformation.get(attributeName)) > highestInformationGain)
            {
                highestInformationGain = this.targetInformation - weightedInformation.get(attributeName);
                highestInformationAttributeName = attributeName;
            }
            try {
                log("Information Gain für " + attributeName + " beträgt " + Double.toString(this.targetInformation - weightedInformation.get(attributeName)) + "\n");
            } catch (IOException ex) {
                Logger.getLogger(ID3Algorithm.class.getName()).log(Level.SEVERE, null, ex);
            }
        }
        
        if(highestInformationGain == 0.0)//this.targetInformation)
        {
            try {
                log("Dieses Zweig endet in einem Blatt mit dem Zielwert "+this.table.get(this.targetAttribute).get(0) +"\n\n");
            } catch (IOException ex) {
                Logger.getLogger(ID3Algorithm.class.getName()).log(Level.SEVERE, null, ex);
            }
            return null;
        }
        else
        {
            Map<String,Double> result = new HashMap<String, Double>();
            result.put(highestInformationAttributeName, highestInformationGain);
            try {
                log("Ausgewähltes Attribut: " + highestInformationAttributeName + " mit Information Gain "+ highestInformationGain +"\n\n");
            } catch (IOException ex) {
                Logger.getLogger(ID3Algorithm.class.getName()).log(Level.SEVERE, null, ex);
            }
            return result;
        }
    }
    
    /**
     * Splits the table by the Values of the attribute with the highest Information gain.
     * @param attribute Attribute with the highest Information Gain.
     * @return 
     */
    public Map<String,Map<String,ArrayList>> splitTable(String splitAttribute)
    {
        Map<String,Integer> splitAttributeValues = this.countAttributeValues(splitAttribute);
        Map<String, Map<String,ArrayList>> resultMap = new HashMap<String, Map<String,ArrayList>>();
 
        for(String elem : splitAttributeValues.keySet())
        {
            ArrayList<Integer> indexArray = new ArrayList();
            
            for(int i = 0; i < this.numberOfRows; i++)
            {
                if(this.table.get(splitAttribute).get(i).equals(elem))
                {
                    indexArray.add(i);
                }
            }
            
            Map<String,ArrayList> valueMatchList = new HashMap<String, ArrayList>();
            for(String tblAttr : this.table.keySet())
            {
                if(!tblAttr.equals(splitAttribute))
                {
                    ArrayList attrValues = new ArrayList();
                    for(int i = 0; i < indexArray.size(); i++)
                    {
                        attrValues.add(this.table.get(tblAttr).get(indexArray.get(i)));
                    }
                    valueMatchList.put(tblAttr, attrValues);
                }
            }
            resultMap.put(elem,valueMatchList);
        }
        
        return resultMap;
    }
    
    /**
     * Compares the given attribute with the target attribute and returns the value of hits
     * @param attributeName Name of the attribute that should be compared to the target.
     * @return value of hits
     */
    public Map<String,int[]> compareAttributeAndTarget(String attributeName)
    {
        // Initialize all the values we are going to need
        ArrayList<String> targetAttributeValues = this.table.get(this.targetAttribute); // Values of the target Attribute
        ArrayList<String> compareAttributeValues = this.table.get(attributeName);       // Values of the Attribute we look at
        Map<String,int[]> valueCount = new HashMap<String, int[]>();                    // Map to store the hit/miss ratio
        
        // Fill the Map with the names of the attributes
        for(String elem : this.countAttributeValues(attributeName).keySet())
        {
            valueCount.put(elem, new int[]{0,0});
        }
        
        for(int i = 0; i < this.numberOfRows; i++)
        {
            // Test, if the Value in the Row equals the target Attributes Value that we are looking for
            if(targetAttributeValues.get(i).equals(this.targetAttributeValue))
            {
                int hit = valueCount.get(compareAttributeValues.get(i))[0] + 1;
                valueCount.put(compareAttributeValues.get(i), new int[]{hit, valueCount.get(compareAttributeValues.get(i))[1]});
            }
            else
            {
                int miss = valueCount.get(compareAttributeValues.get(i))[1] + 1;
                valueCount.put(compareAttributeValues.get(i), new int[]{valueCount.get(compareAttributeValues.get(i))[0], miss});
            }
        }
        
        return valueCount;
    }
    
    /**
     * Method to log all calculated values in a log.txt
     */
    public void log(String value) throws IOException
    {        
        FileWriter writer = new FileWriter(this.logFileName, Boolean.TRUE);
        writer.append(value);
        
        writer.flush();
        writer.close();
//        throw new UnsupportedOperationException("Not yet Implemented");
    }
    
    /**
     * Delete the log file to write new
     * @throws IOException 
     */
    public void deleteLog() throws IOException
    {
        FileWriter fw = new FileWriter(new File(this.logFileName),false); //true für append!
        BufferedWriter bw = new BufferedWriter(fw); 
        bw.write(""); 
        bw.close(); 
    }
    
    /**
     * Count the rows of the given table
     * @param tempTable table whos rows should be counted.
     * @return integer with the number of the given tables rows
     */
    public int countTableRows()
    {
        ArrayList rows = this.table.get(this.targetAttribute);
        return rows.size();
    }
    
    /**
     * Count the number of attributes in the table (including the target attribute)
     * @param tempTable The table, which attributes should be counted
     * @return int with the number of attributes
     */
    public int countTableAttributes()
    {
        return this.table.size();
    }
    
    /**
     * Count the different Values of the attribute
     * @param attributeName Name of the attribute in the table which values should be counted.
     * @return returns a Map with the name of the attribute value as String and the integer of the number of occurence
     */
    public Map<String,Integer> countAttributeValues(String attributeName)
    {
        // Get the values of the wanted attribute
        ArrayList<String> attributeValues = this.table.get(attributeName); 
        // initialize the Map that should be returned. 
        Map<String,Integer> countedAttributesAndValues = new HashMap<String, Integer>();
        
        // Iterate though all values in the List and count them. Store the results in the map
        for(int i = 0; i < attributeValues.size();i++)
        {
            String tempAttributeValue = attributeValues.get(i);
            if(countedAttributesAndValues.get(tempAttributeValue) != null)  // Value already exists in Map
            {
                countedAttributesAndValues.put(tempAttributeValue, countedAttributesAndValues.get(tempAttributeValue)+1);
            }
            else // Value did not exist. Is now added.
            {
                countedAttributesAndValues.put(tempAttributeValue, 1);
            }
        }
        
        return countedAttributesAndValues;
    }
}
